package com.zklh.leetcode.chain.problem86;


import com.zklh.leetcode.tree.model.ListNode;

/**
 * 解法
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2023/5/6 10:50
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        // 定义前置结点,  方便返回头结点
        ListNode preNode = new ListNode();
        preNode.next = head;
        ListNode littleLatestNode = preNode;
        ListNode bigLatestNode;
        while (littleLatestNode.next != null && littleLatestNode.next.val < x) {
            littleLatestNode = littleLatestNode.next;
        }
        if (littleLatestNode.next == null) {
            return preNode.next;
        }
        bigLatestNode = littleLatestNode.next;

        while (bigLatestNode.next != null) {
            if (bigLatestNode.next.val < x) {
                ListNode current = bigLatestNode.next;
                bigLatestNode.next = current.next;
                current.next = littleLatestNode.next;
                littleLatestNode.next = current;
                littleLatestNode = current;
            } else {
                bigLatestNode = bigLatestNode.next;
            }
        }
        return preNode.next;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode head = new ListNode(1);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(2);
        System.out.println(solution.partition(head, 3));
    }
}
